\section{Problema 3}

\subsection{Enunciado}
Se tienen k puntos en el plano con coordenadas enteras y se tiene ademas una caja, representada por un
rectangulo de dimensiones dadas. La caja puede ubicarse en cualquier lugar del plano, pero no puede
rotarse, es decir, la base de la caja debe quedar paralela al eje x y la altura de la caja debe quedar
paralela al eje y. Un punto sobre un borde de la caja se considera dentro de la misma. Se desea ubicar
la caja de manera tal que la cantidad de puntos que queden dentro de la caja sea maxima. Escribir un
algoritmo que resuelva este problema con una complejidad temporal de a lo sumo $O(k^3)$.

\subsection{Introducción}
Tenemos $k$ puntos y una caja rectangular de $b x h$. Partiendo de eso la idea sería:

Recorremos los $k$ puntos del plano, por cada uno de esos puntos, recorremos los otros $k-1$ restantes y nos quedamos con todos los que puedan ser alcanzables con la caja desde el punto actual. Es decir, si las coordenadas del punto actual son $(x,y)$ entonces nos quedamos con todos los puntos que están dentro del rectángulo formado por los vértices $(x-b,y-h)$ y $(x+b,y+h)$. Ahora por cada uno de los puntos encontrados posicionamos la caja de forma que dicho punto y el punto actual queden dentro. 

La caja se posiciona, según sea el caso, de las siguientes maneras:

\begin{itemize}
 \item Punto encontrado a la izquierda del actual: Se posiciona la caja usando la coordenada x de dicho punto como la coordenada x de la esquina superior izquierda de la caja y la coordenada y estará dada por la mayor entre la coordenada y de dicho punto y el actual.
 \item Punto encontrado a la derecha del actual: Se posiciona la caja usando la coordenada x del punto actual como la coordenada x de la esquina superior izquierda de la caja y la coordenada y estará dada por la mayor entre la coordenada y del punto encontrado y el actual. 
\end{itemize}

Una vez posicionada la caja recorremos los puntos restantes de nuevo y contamos todos los que quedan dentro de la caja. Finalmente nos quedamos con la solución que más puntos incluyó. 

\subsection{Correctitud}

\subsection{Pseudocódigo}
{\bf TODO}
\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para resolver el problema 3.}
	\label{algo::ej3}
	\begin{algorithmic}
		\Function{ejercicio3}{$base$, $altura$, $puntos$}
			\For{$k \leftarrow [0..|puntos|)$}
				\State var $candidatos$ : lista de puntos
				\For{$j \leftarrow [0..|puntos|) \land k \neq j$}
					\If{$puntos_j$ cae dentro de la zona de $puntos_k$}
						\State agregar $puntos_j$ a $candidatos$
					\EndIf
				\EndFor
				\For{$j \leftarrow [0..|candidatos|)$}
					\State var $res \leftarrow 2$
					\If{$puntos_k < candidatos_j$}
						\State Armar la caja adecuadamente
					\Else
						\State Armar la caja adecuadamente
					\EndIf

					\For{$i \leftarrow [0..|candidatos|) \land i \neq j$}
						\If{$candidatos_i$ cae en la caja}
							\State $res \leftarrow res + 1$
						\EndIf
					\EndFor

					\If{$res > maximo$}
						Guardar res y la caja en maximo
					\EndIf
				\EndFor
			\EndFor
		\EndFunction
	\end{algorithmic}
\end{algorithm}

\subsection{Análisis de Complejidad}
Hay tres ciclos anidados. En el peor caso cada ciclo recorre los $k$ puntos, por lo que
la complejidad es del orden $O(k^3)$.

\subsection{Conclusión}

\subsection{Mediciones}

\newpage
